package com.it.od.lee.leetcode;

/**
 * @author: liminghui
 * @date: 2024/1/27 0:36
 * @version: 1.0
 * @description:
 * lee547 求省份数量, 并查集思路实现
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
 * 返回矩阵中 省份 的数量。
 */
public class Leet547 {
    public static void main(String[] args) {
        int[][] isConnecteds = new int[3][3];
        isConnecteds[0] = new int[]{1, 1, 0};
        isConnecteds[1] = new int[]{1, 1, 0};
        isConnecteds[2] = new int[]{0, 0, 1};
        UF uf = new UF(isConnecteds.length);
        for (int i = 0; i < isConnecteds.length; i++) {
            for (int j = 0; j < isConnecteds[0].length; j++) {
                if (isConnecteds[i][j] == 1) {
                    uf.union(i,j);
                }
            }
        }
        System.out.println(uf.count);
    }

    public static class UF {
        private int[] father;
        private int count;

        public UF(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
                count = n;
            }
        }

        private int find(int x) {
            if (father[x] != x) {
                father[x] = find(father[x]);
            }
            return father[x];
        }

        private void union(int x, int y) {
            int x_fa = find(x);
            int y_fa = find(y);
            if (x_fa != y_fa) {
                father[y_fa] = x_fa;
                count--;
            }
        }

    }

    public static class WeightedUnionFind {
        private int[] id;
        private int[] sz;
        private int count;

        public WeightedUnionFind(int count) {
            this.count = count;
            id = new int[count];
            sz = new int[count];
            for (int i = 0; i < count; i++) {
                id[i] = i;
                sz[i] = 1;
            }
        }

        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }

        public void union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot) {
                return;
            }
            if (sz[pRoot] > sz[qRoot]) {
                sz[pRoot] += sz[qRoot];
                id[qRoot] = id[pRoot];
            } else {
                sz[qRoot] += sz[pRoot];
                id[pRoot] = id[qRoot];
            }
            count--;
        }

        public int getCount() {
            return count;
        }

        //find the root of the current node
        private int find(int p) {
            while (p != id[p]) {
                id[p] = id[id[p]];
                p = id[p];
            }
            return p;
        }
    }
}
